package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-30 15:09
 **/
public class LeetCode128 {

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;

        //将数组中元素添加到集合中
        for (int num : nums) {
            set.add(num);
        }

        int max = 0;

        //遍历集合,找出最长序列
        for (int num : set) {

            //只有是一个序列的开头才进行连续序列的查找
            if (!set.contains(num - 1)) {
                int curNum = num;
                int curLen = 1;

                while (set.contains(curNum + 1)) {
                    curNum += 1;
                    curLen += 1;
                }

                max = Math.max(max, curLen);
            }
        }

        return max;
    }

    /*public int longestConsecutive(int[] nums) {
        int n = nums.length;

        //数组为空直接返回0
        if (n == 0) {
            return 0;
        }

        SortedSet<Integer> set = new TreeSet<>();
        //将数组中的元素添加到有序集合中
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
        }

        //集合大小
        int size = set.size();
        int l = 0;
        int r = 0;
        int pre = 0;
        int max = 1;

        for (int num : set) {
            if (r == l) {
                ++r;
                pre = num;
                continue;
            }

            if (num != pre + 1) {
                max = Math.max(max, r - l);
                l = r;
            }

            pre = num;
            ++r;
        }


        return Math.max(max, r - l);
    }*/

    public static void main(String[] args) {
        LeetCode128 code = new LeetCode128();
        System.out.println(code.longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1}));
        System.out.println(code.longestConsecutive(new int[]{100,4,200,1,3,2}));
    }

}
